Programmable integrated circuits (ICs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect and programmable logic. The programmable interconnect typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect and programmable logic are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Other types of programmable ICs can include complex programmable logic devices (CPLDs), programmable logic arrays (PLAs), and programmable array logic (PAL) devices. For all of these programmable ICs, the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other programmable ICs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These programmable ICs are known as mask programmable devices. Programmable ICs can also be implemented in other ways, e.g., using fuse or antifuse technology. The phrase “programmable IC” can include but is not limited to these exemplary devices and can encompass devices that are only partially programmable. For example, one type of programmable IC includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
As noted, programmable ICs can include a variety of different programmable hardware units, e.g., tiles in the case of an FPGA which include LUTs, flip-flops, memory blocks, and the like. These programmable hardware units are distributed on the programmable IC in a regular pattern. To implement a circuit design, each of the hardware units must be programmed, e.g., configured, to implement or function as a particular circuit component of the circuit design. Many components also require a global clock to function. A global clock refers to a periodic signal used to synchronize computational tasks of a circuit.
Most programmable ICs can support multiple global clocks. Each computational element can be synchronized by any of the global clocks on the device. Most programmable ICs will include M global clocks, where M is an integer that is greater than zero. Due to the highly programmable nature of programmable ICs, it is typically the case that only a limited number of the global clocks can be distributed to any one clock region. A “clock region” refers to a physical area or portion on the programmable IC, such as a rectangular area on the programmable IC. Thus, while the programmable IC may have M global clocks, only N global clocks are available in any single clock region, where N is an integer that is less than M.
Assigning a component of the circuit design to a particular hardware unit of the programmable IC so that the hardware unit is programmed to perform the function of the component is referred to as “placing” the component on the programmable IC. The term “site” is used to represent the hardware unit at a particular location on the programmable IC. Thus, components of the circuit design must be placed at sites on the programmable IC in a manner that does not result in more than N clocks being present in any one clock region. This process is referred to as clock domain partitioning or partitioning a circuit design into clock domains.
When performing clock domain partitioning, it is useful not only to generate a solution that does not violate clock domain constraints, but also to generate a solution that achieves satisfactory timing results. Conventional techniques for clock domain partitioning, however, are unable to detect scenarios in which a solution that does not violate clock domain constraints does not exist. In such cases, the circuit design is infeasible since no solution exists that may be practically implemented within the selected programmable IC. In cases where a solution does exist that does not violate clock domain constraints, conventional methods of performing clock domain partitioning are not always able to determine the solution.